

class ListNode:
    def __init__(self,val=0,next=None):
        self.val=val
        self.next=next
class TreeNode:
    def __init__(self,val=0,left=None,right=None):
        self.val=val
        self.left=left
        self.right=right


print("判断是不是相同的树")
def isSameTree(p:TreeNode,q:TreeNode):
    if not p and not q:
        return True
    if not p or not q:
        return False
    if p.val!=q.val:
        return False
    return isSameTree(p.left,q.left) and isSameTree(p.right,q.right)


print("判断是不是对称二叉树")
def isSymmetric(root:TreeNode)->bool:
    def zuoyouduichen(left:TreeNode,right:TreeNode):
        if not left and not right:
            return True
        if not left or not right:
            return False
        if left.val!=right.val:
            return False
        return zuoyouduichen(left.left,right.right) and zuoyouduichen(left.right,right.left)
    if not root:
        return False
    else:
        return zuoyouduichen(root.left,root.right)


print("二叉树的最大深度")
def maxDepth(root:TreeNode)->int:
    if not root:
        return 0
    return max(maxDepth(root.left),maxDepth(root.right))+1

print("判断是不是平衡二叉树"
      "二叉树的每个节点的左右子树的高度差的绝对值不超过 1，则二叉树是平衡二叉树。"
      "根据定义，一棵二叉树是平衡二叉树，当且仅当其所有子树也都是平衡二叉树，因此可以使用递归的方式判断二叉树是不是平衡二叉树，"
      "递归的顺序可以是自顶向下或者自底向上。"
      "1、每一个节点的左子结点和右子节点高度不能大于1"
      "2、每一个节点同时也是平衡二叉树"
      "3、空节点也是平衡二叉树")
def isBalanced(root:TreeNode)->bool:
    def inner_height(node:TreeNode):
        if not node:
            return 0
        return max(inner_height(node.left),inner_height(node.right))+1
    if not root:
        return True
    else:
        return abs(inner_height(root.left)-inner_height(root.right))<=1 and isBalanced(root.left) and isBalanced(root.right)

print("树的最小深度")
def minDepth(root:TreeNode)->int:
    if not root:
        return 0
    if not root.left:
        return minDepth(root.right)+1
    if not root.right:
        return minDepth(root.left)+1
    return min(minDepth(root.left),minDepth(root.right))+1


print("路径总和"
      "判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。"
      "如果存在，返回 true ；否则，返回 false 。")
def lujingzonghe(root:TreeNode,targetSum:int)->bool:

    if not root:
        return False
    targetSum=targetSum-root.val
    if root.left is None and root.right is None:
        return targetSum==0
    return lujingzonghe(root.left,targetSum) or lujingzonghe(root.right,targetSum)

print("二叉树的前序遍历、中序遍历、后序遍历")
def qianxubianli(root:TreeNode)->list[int]:
    res=[]
    def inner(node:TreeNode):
        if not node:
            return
        res.append(node.val)
        inner(node.left)
        inner(node.right)
    inner(root)
    return res

print("完全二叉树的节点个数")
def countNodes(root:TreeNode) ->int:
    if not root:
        return 0
    return countNodes(root.left)+countNodes(root.right)+1

print("反转二叉树")
class TreeNode:
    def __init__(self,val=0,left=None,right=None):
        self.val=val
        self.left=left
        self.right=right
def fanzhuanerchashu(root:TreeNode)->TreeNode:
    if not root:
        return None
    left=fanzhuanlianbiao(root.left)
    right=fanzhuanlianbiao(root.right)
    root.left=right
    root.right=left
    return root

print("给定二叉树的根节点 root ，返回所有左叶子之和")
def zuoyezihe(root:TreeNode)->int:
    sum=0
    def inner(node:TreeNode):
        if not node:
            return 0
        if node.left and node.left.left is None and node.left.right is None:
            nonlocal sum
            sum=sum+node.left.val
        inner(node.left)
        inner(node.right)
    inner(root)
    return sum
print("回文链表")
def huiwenlianbiao(head:ListNode)->bool:
    if not head:
        return False
    current=head
    tem=[]
    while current:
        tem.append(current.val)
        current=current.next
    return tem==tem[::-1]

print("返回相交链表的相交节点")
def xiangjiaojiedian(headA:ListNode,headB:ListNode)->ListNode:
    if not headA or not headB:
        return None
    current=headA
    tem=[]
    while current:
        tem.append(current)
        current=current.next
    current=headB
    while current:
        if current in tem:
            return current
        current=current.next
    return None


print("反转链表")
def fanzhuanlianbiao(head:ListNode)->ListNode:
    if not head:
        return None
    pre=None
    current=head
    while current:
        tem=current.next
        current.next=pre
        pre=current
        current=tem
    return pre

print("移除链表元素"
      "给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点")
def yichulianbiaoyuansu(head:ListNode,val:int)->ListNode:
    if not head:
        return None
    new_head=ListNode()
    new_head.next=head
    current=new_head
    while current.next:
        if current.next.val==val:
            current.next=current.next.next
        else:
            current=current.next
    return new_head.next


print("判断是不是环形链表")
def huanxinglianbiao(head:ListNode)->bool:
    if not head:
        return False
    fast=head
    slow=head
    while fast:
        if not fast.next or not fast.next.next:
            return False
        fast=fast.next.next
        slow=slow.next
        if fast==slow:
            return True


print("删除排序链表中的重复元素")
def shanchuchongfuyuansu(head:ListNode)->ListNode:
    if not head:
        return None
    current=head
    while current.next:
        if current.val==current.next.val:
            current.next=current.next.next
        else:
            current=current.next
    return head